/*
 * priorunqueue.h
 *
 *  Created on: 2011-5-25
 *      Author: chenl
 */

#ifndef PRIORUNQUEUE_H_
#define PRIORUNQUEUE_H_

#include "taskqueue.h"
#include "common/common_bit.h"

inline int sched_find_first_bit(const uint32_t *b)
{
	if (unlikely(b[0]))
		return __ffs(b[0]);
	if (unlikely(b[1]))
		return __ffs(b[1]) + 32;
	if (unlikely(b[2]))
		return __ffs(b[2]) + 64;
	if (b[3])
		return __ffs(b[3]) + 96;
	return __ffs(b[4]) + 128;
}

class CPrioRunQueue: public ITaskQueue
{
public:
	enum
	{
		enmMaxPriority = 140, enmBitMapSize = enmMaxPriority / 32 + 1,
	};
	typedef struct tagRunQueue
	{
		int nr_active;
		uint32_t bitmap[enmBitMapSize];
		CTaskQueue queue[enmMaxPriority];
	} RunQueue;
public:
	CPrioRunQueue();
	virtual ~CPrioRunQueue();

public:
	virtual int32_t Initialize();
	virtual int32_t Uninitialize()
	{
		return S_OK;
	}
	virtual int32_t InsertTask(CTask&);
	virtual int32_t DeleteTask(CTask&);
	virtual bool IsTaskOnQueue(const CTask&);
	virtual bool IsEmtpy() const
	{
		return 0 == nr_running ? true : false;
	}
	virtual bool IsFull() const
	{
		return false;
	}
	virtual CTask* FirstTask();
	virtual CTask* NextTask(CTask&);
	virtual CTask* Pop()
	{
		return NULL;
	}
	virtual int32_t MoveTaskToTail(CTask&)
	{
		return S_FALSE;
	}

	void SwitchArray()
	{
		RunQueue* p = pActiveQueue;
		pActiveQueue = pExpireQueue;
		pExpireQueue = p;
	}

	int32_t SwapOutTask(CTask& task);

	int32_t SwapTask(CTaskQueue::TaskQueueItr itr, CTaskQueue* pFromQueue,
			CTaskQueue* pToQueue);
	//僅搜索priority對應的隊列
	int32_t FindTask(const CTask&, RunQueue& runqueue,
			CTaskQueue::TaskQueueItr&, CTaskQueue&);
	//搜索全部隊列
	int32_t SearchTask(const CTask&, RunQueue& runqueue,
			CTaskQueue::TaskQueueItr&, CTaskQueue&);

protected:
	CTask* FirstTask(RunQueue&);
	CTask* NextTask(RunQueue&, CTask&);

public:
	friend class CScheduler_O_1;

private:
	unsigned long 		nr_running;
	unsigned long 		nr_switching;
	unsigned long 		nr_uninterruptible;
	unsigned long 		expired_timestamp;
	unsigned long long 	timestamp_last_tick;
	unsigned long 		nr_switches;
	int 				best_expired_prio;
	RunQueue* 			pActiveQueue;
	RunQueue* 			pExpireQueue;

	RunQueue 			taskQueue_[2];

};

#endif /* PRIORUNQUEUE_H_ */
